class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> low;
        low.push_back(nums[0]);
        for(int i = 1; i < nums.size(); ++i){
            if(low.back() < nums[i])
                low.push_back(nums[i]);
            else{
                // lower_bound 返回找到位置的迭代器
                *(lower_bound(low.begin(), low.end(), nums[i]))=nums[i];
            }
        }
        return low.size();
    }
};